package com.ryujung.dfs_backtracking;

import java.util.*;

class Solution90 {
    /**
     * 解答成功:
     * 执行耗时:1 ms,击败了99.24% 的Java用户
     * 内存消耗:41.3 MB,击败了98.24% 的Java用户
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        Deque<Integer> stk = new ArrayDeque<>();
        dfs(nums, 0, stk, res);
        return res;
    }

    private void dfs(int[] nums, int index, Deque<Integer> stk, List<List<Integer>> res) {
        res.add(new ArrayList<>(stk));

        for (int i = index; i < nums.length; i++) {
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }
            stk.addLast(nums[i]);
            dfs(nums, i + 1, stk, res);
            stk.removeLast();
        }
    }

    public static void main(String[] args) {
        Solution90 s = new Solution90();
        System.out.println(s.subsetsWithDup(new int[]{1, 2, 2}));
        System.out.println(s.subsetsWithDup(new int[]{4, 4, 4, 1, 4}));
    }
}